package treeCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @version v1.0
 * @Description: 二叉树的中序遍历；
 * 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
 * @Author: daijinwu
 * @Date: 2021/5/12
 */
public class Tree94 {


    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.setLeft(null);
        TreeNode treeNode2 = new TreeNode(2);
        treeNode.setRight(treeNode2);
        treeNode2.setRight(null);
        TreeNode treeNode3 = new TreeNode(3);
        treeNode2.setLeft(treeNode3);
        System.out.println(inorderTraversal(null));
    }

    /**
     * 中序遍历 -- 递归解法
     * @param root root
     * @return
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        return traversal(new ArrayList<>(), root);
    }

    public static List<Integer> traversal(List<Integer> list, TreeNode node) {
        if (node == null) {
            return list;
        }
        traversal(list, node.left);
        list.add(node.val);
        traversal(list, node.right);
        return list;
    }

//    /**
//     * 树结构
//     */
//    public static class TreeNode {
//        int val;
//        TreeNode left;
//        TreeNode right;
//        TreeNode() {}
//        TreeNode(int val) { this.val = val; }
//        TreeNode(int val, TreeNode left, TreeNode right) {
//            this.val = val;
//            this.left = left;
//            this.right = right;
//        }
//
//        public void setLeft(TreeNode left) {
//            this.left = left;
//        }
//
//        public void setRight(TreeNode right) {
//            this.right = right;
//        }
//    }

}
